//从前序与中序遍历序列构造二叉树
class SolutionCreateTree {
    public int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChile(preorder,inorder,0,inorder.length-1);
  }

    public TreeNode buildTreeChile(int[] preorder, int[] inorder,int inbegin,int inend) {
        if(inbegin > inend){
            return null;//没有左树 或者没有右树
        }

        TreeNode root = new TreeNode(preorder[preIndex]);

        int rootIndex = findIndexRoot(inorder,inbegin,inend,preorder[preIndex]);
        if(rootIndex == -1){
            return null;
        }
        
        preIndex++;

        root.left = buildTreeChile(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChile(preorder,inorder,rootIndex+1,inend);

        return root;
    }

        
    private int findIndexRoot(int[] inorder,int inbegin,int inend,int key){
        for(int i = inbegin;i <= inend;i++){
            if(inorder[i] == key){
                return i;
            }   
        }  
        return -1;     
    }
}